// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
)

// This function implements QuickSort algorithm to sort a given integer slice in ascending order
func QuickSort(array []int) []int {
	// Set low and high index values for the slice
	low, high := 0, len(array)-1
	// If slice is empty or contains only one element, it is already sorted so return nil
	if low >= high {
		return nil
	}
	// Call the Partition function to find the pivot point
	part := Partition(array, low, high)
	// Recursively call the QuickSort function to sort the left and right sub-arrays
	QuickSort(array[:part])
	QuickSort(array[part+1:])
	// Return the sorted integer slice
	return array
}

// 此函数根据枢轴点划分给定的整数切片并返回枢轴索引
func Partition(array []int, low, high int) int {
	// 将枢轴值设置为切片的最后一个元素
	pivot := array[high]
	// 将第 i 个索引初始化为比 low 索引小一
	i := low - 1
	// 从低索引到高索引遍历切片 - 1
	for j := low; j < high; j++ {
		// 如果当前元素小于枢轴，则与第（i+1）个位置的元素交换
		if array[j] < pivot {
			i++
			array[j], array[i] = array[i], array[j]
		}
	}
	// 将枢轴元素与第 (i+1) 个位置的元素交换，将枢轴放在正确的位置
	array[i+1], array[high] = array[high], array[i+1]
	return i + 1
}

func main() {
	array := []int{33, 23, 56, 7, 8, 18, 99, 28}
	QuickSort(array)
	fmt.Println(array)
}

//$ go run quickSort.go
//[7 8 18 23 28 33 56 99]
